#!/usr/bin/env python
# -*- coding: utf-8 -*-

# @Time     :2020/12/13
# @Author   :Changshu
# @File     :Exercise_572.py
# 572. 另一个树的子树
# 给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。
# s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。

# Definition for a binary tree node.
class TreeNode:
	def __init__(self, val=0, left=None, right=None):
		self.val = val
		self.left = left
		self.right = right


'''法一：递归，没遍历一个节点，就使用深度优先检查一次是否是子树'''
class Solution:
	def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
		return self.dfs(s,t)

	def check(self,s: TreeNode, t: TreeNode):
		if not s and not t:
			return True
		if (not s and t) or (s and not t) or (s.val!=t.val):
			return False
		return self.check(s.left,t.left) and self.check(s.right,t.right)

	def dfs(self,s: TreeNode, t: TreeNode):
		if not s:
			return False
		return self.check(s,t) or self.dfs(s.left,t) or self.dfs(s.right,t)

